package com.example.demo.calc;

import lombok.Data;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

public class BinaryTree {

    /**
     * 二叉树节点
     *
     * @return
     */
    @Data
    public static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }
    }

    /**
     * 构建二叉树
     *
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        Integer data = inputList.removeFirst();
        // 这里的判断很关键，如果为空，则不再进行下一步
        if (data != null) {
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 二叉树前序遍历
     */
    public static void preOrderTraverse(TreeNode node){
        if(node == null){
            return;
        }

        System.out.print(node.data);
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }

    /**
     * 二叉树中序遍历
     */
    public static void inOrderTraverse(TreeNode node){
        if(node == null){
            return;
        }

        inOrderTraverse(node.leftChild);
        System.out.print(node.data);
        inOrderTraverse(node.rightChild);
    }

    /**
     * 二叉树后序遍历
     */
    public static void postOrderTraverse(TreeNode node){
        if(node == null){
            return;
        }

        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        System.out.print(node.data);
    }

    /**
     * 测试代码
     * @param args
     */
    public static void main(String[] args) {
        Integer[] integers = {3, 2, 9, null, null, 10, null, null, 8, null, 4};
        LinkedList<Integer> inputList = new LinkedList<>();
        Arrays.stream(integers).forEach(arr ->{
            inputList.add(arr);
        });
        TreeNode binaryTree = createBinaryTree(inputList);
        System.out.println("前序遍历: ");
        preOrderTraverse(binaryTree);
        System.out.println("");

        System.out.println("中序遍历: ");
        inOrderTraverse(binaryTree);
        System.out.println("");

        System.out.println("后序遍历: ");
        postOrderTraverse(binaryTree);

    }
}
